package daily.year2024.m10;

/**
 * 97. 交错字符串
 *
 * @author wjs 2024/10/23
 */
public class d23 {
    //解法一：动态规划
    class Solution1 {
        public boolean isInterleave(String s1, String s2, String s3) {
            char[] c1 = s1.toCharArray(), c2 = s2.toCharArray(), c3 = s3.toCharArray();
            int m = c1.length, n = c2.length, l = c3.length;
            if(l != m + n) {
                return false;
            }
            boolean[][] dp = new boolean[m+1][n+1];
            dp[0][0] = true;
            for(int i=0;i < m;i++) {
                if(c1[i] == c3[i]) {
                    dp[i+1][0] = dp[i][0];
                }
            }
            for(int i=0;i < n;i++) {
                if(c2[i] == c3[i]) {
                    dp[0][i+1] = dp[0][i];
                }
            }
            for(int i=1;i <= m;i++) {
                for(int j=1;j <= n;j++) {
                    int t = i+j-1;
                    if(c1[i-1] == c3[t]) {
                        dp[i][j] = dp[i-1][j];
                    }
                    if(c2[j-1] == c3[t]) {
                        dp[i][j] = dp[i][j] || dp[i][j-1];
                    }
                }
            }
            return dp[m][n];
        }
    }
}
